//深度和广度优先搜索算法：核心原理：构造存储结果和使用队列进行遍历
//原文链接：https://blog.csdn.net/weixin_40953222/article/details/80544928?utm_source=app&app_version=4.11.0&code=app_1562916241&uLinkId=usr1mkqgl919blen
#include <iostream>
#include <queue>

using namespace std;

#define MVNum  (100)				//表示最大顶点个数
//存储结构:邻接矩阵存储表示
typedef struct AMGraph
{
	char vexs[MVNum];				//顶点表
	int  arcs[MVNum][MVNum];		//领接矩阵：点与点的连接情况
	int  vexnum, arcnum;			//当前的顶点数和边数
}AMGraph;

//找到顶点v的对应下标:Vx存放的位置
int LocateVex(char v, AMGraph &g)
{
	int i;
	for (int i = 0; i < g.vexnum; i++)
	{
		if (g.vexs[i] == v)
		{
			return i;
		}
	}
}

//采用邻接矩阵表示法，创建无向图G
int CreateUDG_1(AMGraph &g)
{
	int i, j, k;
	char v1, v2;
	scanf("%d%d", &g.vexnum, &g.arcnum);
	getchar();

	for (i = 0; i < g.vexnum; i++)
	{
		scanf("%c", &g.vexs[i]);
	}

	for (i = 0; i < g.vexnum; i++)
	{

		for (j = 0; j < g.vexnum; j++)
		{
			//初始化都为无边
			g.arcs[i][j] = 0;
		}
	}

	for (i = 0; i < g.arcnum; i++)
	{
		getchar();
		scanf("%c%c", &v1, &v2);
		int k1 = 0, k2 = 0;
		k1 = LocateVex(v1,g);
		k2 = LocateVex(v2, g);
		g.arcs[k1][k2] = 1;  //k1 k2默认不会越界
		g.arcs[k2][k1] = 1;
	}
	return 1;
}

queue<char> q;						//定义一个队列，使用库函数queue
bool visited[MVNum];		        //定义一个visited数组，记录已被访问的顶点

//采用邻接矩阵表示图的广度优先遍历
void BFS_AM(AMGraph &G, char v0)
{
	int u = 0, i = 0, v = 0, w = 0;
	v = LocateVex(v0,G);
	printf("%c ", v0);
	visited[v] = 1;

	q.push(v0);
	while (!q.empty())
	{
		u = q.front();
		v = LocateVex(u, G);
		q.pop();

		for (i = 0; i < G.vexnum; i++)//最关键的一步，找到同层的第一个，还可以继续找第二个，直到所有的都遍历一次：所以效率很低的
		{
			w = G.vexs[i];
			if (G.arcs[v][w] == 1 && !visited[i])
			{
				printf("%c", w);
				q.push(w);
				visited[i] = 1;
			}
		}
	}

}

void DFS_AM(AMGraph &G, int v)
{
	int w;
	printf("%c ", G.vexs[v]);
	visited[v] = 1;
	for (w = 0; w < G.vexnum; w++)
	if (G.arcs[v][w] && !visited[w]) //递归调用
		DFS_AM(G, w);
}



int main()
{


}